package com.buercorp.wangyu.buerlinkedlist;

import com.buercorp.wangyu.abstractclass.AbstractList;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 手写 LinkedList
 *
 * @param <E>
 * @author wangyu
 */
public class LinkedList<E> extends AbstractList<E> implements Iterable<E>{
    private Node first;
    private Node last;


    public Iterator iterator(){
        return new Iterator<E>() {
            @Override
            public boolean hasNext() {
                return first != null;
            }

            @Override
            public E next() {
                if (!hasNext()){
                    throw new NoSuchElementException();
                }
                E element = (E) first.element;
                first = first.next;
                return element;
            }
        };
    }


    private static class Node<E> {
        Node<E> pre;
        Node<E> next;
        E element;

        public Node(Node pre, Node next, E element) {
            this.pre = pre;
            this.next = next;
            this.element = element;
        }
    }


    @Override
    public E get(int index) {
        // 检查索引越界
        checkElementIndex(index);
        return node(index).element;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index)) {
            throw new IndexOutOfBoundsException(": Index: " + index + ": Size: " + size);
        }
    }

    private boolean isElementIndex(int index) {
        // 满足条件
        return index >= 0 && index < size;
    }

    private Node<E> node(int index) {
        Node currentNode = first;
        // 判断要查找的 index 时靠近头还是靠近尾 如果靠近头 从头开始找   index ？ size / 2
        if (index > size >> 1) {
            // 从尾开始找
            currentNode = last;
            for (int i = size - 1; i > index; i--) {
                currentNode = currentNode.pre;
            }
        } else {
            for (int i = 0; i < index; i++) {
                currentNode = currentNode.next;
            }
        }
        return currentNode;
    }

    @Override
    public E set(int index, E element) {
        // 检查索引越界
        checkElementIndex(index);
        // 在指定索引上去修改元素值是 element 返回原来的值
        // 1.获得 index 上的 node 2.拿到原来的老值 3.去进行修改 4.return 原来的老值
        Node<E> node = node(index);
        E oldElement = node.element;
        node.element = element;
        return oldElement;
    }

    @Override
    public void add(int index, E element) {
        checkPostionIndex(index);
        if (index == size) {
            // 插入零号角标 添加到末尾 没有元素的时候
            linkLast(element);
        } else {
            linkBefore(element, node(index));
        }
        size++;
    }

    private void linkBefore(E element, Node<E> node) {
        Node<E> pre = node.pre;
        Node<E> newNode = new Node(pre, node, element);
        node.pre = newNode;
        if (pre == null) {
            first = newNode;
        } else {
            pre.next = newNode;
        }
    }

    /**
     * 拿到last 节点
     * 构建node 完成他的指向关系
     * 将原来的last 节点 next 修改成 新构建出来的 node
     * 将链表的 last 进行修改
     *
     * @param element
     */
    private void linkLast(E element) {
        Node l = last;
        Node newNode = new Node(l, null, element);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
    }

    private void checkPostionIndex(int index) {
        if (!isPostionIndex(index)) {
            throw new IndexOutOfBoundsException(": Index: " + index + "Size: " + size);
        }
    }

    private boolean isPostionIndex(int index) {
        return index >= 0 && index <= size;
    }

    /***
     *
     * 1.获取要删除的元素 Node
     * 2.获取前一个节点
     * 3.获取他的后一个节点
     * 4.需要改变前一个节点的 next
     * 5.改变后一个节点 pre
     * @param index
     * @return
     */
    @Override
    public E remove(int index) {
        checkElementIndex(index);
        Node<E> node = node(index);
        Node<E> pre = node.pre;
        Node<E> next = node.next;

        if (pre == null) {
            first = next;
            next.pre = null;
        } else {
            pre.next = next;
        }

        if (next == null) {
            last = pre;
        } else {
            next.pre = pre;
        }
        size--;
        return node.element;
    }

    /***
     * 查找有没有 element 元素 如果有返回 element 元素的索引 如果没有则返回 -1
     */
    @Override
    public int indexOf(E element) {
        Node x = first;
        int index = 0;
        if (element == null) {
            for (Node i = x; i != null; i = i.next) {
                if (element == i.element) {
                    return index;
                }
                index++;
            }
        } else {
            for (Node i = x; i != null; i = i.next) {
                if (element.equals(i.element)) {
                    return index;
                }
                index++;
            }
        }
        return -1;
    }

    @Override
    public void clear() {
        size = 0;
        // GC可达算法 垃圾回收
        first = null;
        last = null;
    }

    @Override
    public E Iteratore() {
        return (E) iterator();
    }



    @Override
    public String toString() {
        if (size == 0) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder().append("[");
        Node x = first;
        for (Node i = x; i != null; i = i.next) {
            sb.append(i.element);
            if (i.next == null) {
                return sb.append("]").toString();
            }
            sb.append(",");
        }
        return sb.toString();
    }

    private class LinkedListIterator implements Iterator<E> {
        private Node<E> current = first;

        public boolean hasNext() {
            return current != null;
        }

        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E data = current.element;
            current = current.next;
            return data;
        }
    }


}



